/**
 * @file 017.含有所有字符的最短字符串.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-12-09
 *
 * @copyright Copyright (c) 2021
 *
 */

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

template <typename T>
void print(const T &t)
{
    typename T::const_iterator it = t.begin();
    cout << "[";
    while (it != t.end() - 1) {
        cout << *it++ << ", ";
    }
    cout << *it++ << "]";
    cout << endl;
}

class Solution
{
public:
    string minWindow(string s, string t)
    {
        unordered_map<int, int> tMap;   // t{字符：次数}
        unordered_map<int, int> winMap; // 窗口{字符：次数}
        int i = 0;
        int match = 0; // 记录匹配字符个数
        string sub;
        for (char &ch : t) {
            tMap[ch] += 1;
        }
        for (int j = 0; j < s.length(); ++j) {
            auto it = tMap.find(s[j]);
            if (it != tMap.end()) { // winMap只计算窗口内含t的字符
                winMap[s[j]] += 1;
                if (winMap[s[j]] == tMap[s[j]]) {
                    ++match;
                }
            }
            // 已匹配时 tMap和winMap 完全相同
            while (match == tMap.size()) {
                // 寻找最小子串
                if (j - i + 1 < sub.length() || sub.empty()) {
                    sub = s.substr(i, j - i + 1);
                }
                // 对窗口左端点动手
                auto it = winMap.find(s[i]);
                if (it != winMap.end()) {
                    winMap[s[i]] -= 1;
                    if (winMap[s[i]] < tMap[s[i]]) {
                        --match;
                    }
                    if (winMap[s[i]] == 0) {
                        winMap.erase(s[i]);
                    }
                }
                ++i;
            }
        }
        return sub;
    }
};

int main()
{
    cout << Solution().minWindow("ADOBECODEBANC", "ABC") << endl;
    cout << Solution().minWindow("a", "a") << endl;
    cout << Solution().minWindow("a", "aa") << endl;
    return 0;
}